\chapter{Conclusions}
In this chapter the main results of the thesis are summarized and directions for further work are discussed.

\section{Summary}
A lot of architectural choices are possible when building upcoming chip multiprocessors CMP or, more in general, multiprocessors: parallelism degree of the architecture, complexity of the processing nodes itself, interconnection networks, memory hierarchy, cache coherence protocols and many others. In particular, the functional sharing of resources is fundamental to optimize the \textit{global performance of the architecture}; unfortunately, this has also a side effect, that is the complexity of \textit{predicting} the \textit{single flow performance}. In the perspective of structured parallel programming, a \textit{performance cost model} would be of invaluable importance to allow a compiler to evaluate, configure and optimize parallel programs. In this thesis we addressed the problem of formalizing this cost model.

\paragraph{Analytical resolution techniques for client-server models}
Our starting point was the cost model defined in~\cite{VAN}. As far as we know, it is the only architectural cost model based on the idea of retrieving a precise estimation of the application performance by resorting on a \textit{detailed} and \textit{machine-dependent} prediction. In~\cite{VAN}, the shared memory architecture is modeled as a client-server system with request-reply behaviour. The aim of this modeling is to determine the response time of the server, which actually corresponds to the under-load memory access latency $R_Q$. By exploiting basic Queueing Theory results, a first analytical resolution technique $S$ is provided. $S$ is an \textit{approximate} resolution technique, i.e. it relies on some assumptions and hypothesis, but it is also extremely \textit{simple} from the mathematical point of view. 

The first objective of the thesis was to validate the accuracy of $S$, with emphasis on CMP architectures. The comparison between simulations and analytical results states that \textit{$S$ overestimates $R_Q$ as soon as the number of conflicts for accessing a memory macro-module becomes significant}. The second goal of the thesis was to overcome this problem. Therefore, we proposed a new resolution technique $FP$ (''Finite Population''). $FP$ exploits the idea that the population in a client-server system is \textit{fixed}, thus the interarrival rate at the server cannot be assumed constant as in $S$. $FP$ matches the simulation results almost exactly, but it works only for exponential servers, since it is based on pure Markovian Theory. 

\paragraph{Numerical resolution techniques for client-server models}
The modeling of far complex architectures implies changes to the semantics of the client-server system. For instance, we have pointed out the necessity of modeling load-dependent servers and hierarchical architectures; even a less abstract representation of the application workload could provide meaningful improvements, as shown in~\cite{ALBE}. In light of these elements, we proposed a new approach to the modeling of such systems, based on a \textit{stochastic process algebra}. We introduced PEPA and its relationship with the Markovian Theory. Therefore, we moved from analytical resolution techniques to numerical ones. A side effect of the PEPA modeling is an improvement to the accuracy of the $R_Q$ prediction. All the work on PEPA has been undertaken according to the classical principles: simplicity of the approach (which explains also the choice of the language) and quality of the approximated results. 

\paragraph{Quantitative analysis of client-server systems}
We validated both analytical and numerical techniques against direct experimentation. Table~\ref{summary} summarizes the results we achieved by showing the maximum percentage estimation error for a not congested memory macro-module. 
\begin{table}[h]
\begin{center}
\begin{tabular}{ c | c || c || c |}
\cline{2-4}
 & \multicolumn{3}{|c|}{Techniques} \\ \cline{2-4}
 & $S$ &  $FP$ & $PEPA$ \\\hline
\multicolumn{1}{|c|}{Exponential} & 23.57$\%$ & 0.93$\%$ & 0.93$\%$ \\\hline
\multicolumn{1}{|c|}{Deterministic} & 20.07$\%$ & - & 5.88$\%$ \\\hline
\end{tabular}
\caption{Analytical and numerical resolution techniques for client-server models. In each cell the \textit{maximum relative error} for a not congested server is showed.}
\label{summary}
\end{center}
\end{table} 


\paragraph{The methodology applied to a concrete architecture}
A cost model for a concrete architecture, the Tile64, has been provided and validated. In this part of the thesis we worked in two directions.
\begin{enumerate}
\item The architecture has been analysed to derive constants and parameters of the cost model. An in-depth study of the memory system, as well as network latencies, characterize our work. In this experimentation phase, the Tile64 profiler has been extensively used.  
\item A client-server system with load-dependent semantics, expressed in PEPA, has been used to formalize the Tile64 cost model. A simple parallel application has been chosen and algorithm-dependent parameters have been extracted. At this point, we were able to instantiate and validate the Tile64 cost model. 
\end{enumerate}
The accuracy of the predicted $R_Q$ turned out fairly good. Clearly, further experiments should be done with different, far complex parallel applications.

\section{Further work}
Guidelines on how to advance the research go in many directions. 
\begin{enumerate}
\item \textbf{Analytical techniques.} The goal is to extend the techniques of Chapter~\ref{clientserver} to model those aspects that suggested the employment of PEPA. The problem is always the same: find a \textit{simple} yet \textit{fairly accurate} resolution approach, as the one based on a system of linear equations. 
\item \textbf{Application's workload.} The cost model we provided for the Tile64 in Chapter~\ref{TILERA} should be validated with more complex applications, e.g. data parallel computations with stencils or even composed skeletons. In this perspective, the cost model may be extended with the techniques formalized in~\cite{ALBE}, e.g. client-server with heterogeneous clients, computational phases for a more detailed workload model, etc.
\item \textbf{Hierarchical systems.} A cost model for hierarchical systems has been already formalized by means of PEPA~\cite{ALBE}. The knowledge we matured on the Tilera architecture could be exploited to validate the accuracy of this cost model: upcoming Tilera CMPs are hierarchical systems, though their firmware-assembler architecture resembles the basic one of the Tile64. 
\item \textbf{Abstract architecture cost model.} Once found, the under-load memory access latency should be used to express the two fundamental functions of our abstract architecture: $T_{send}$ and $T_{calc}$. Following the methodology of~\cite{VAN} and taking into account the specific features of the run-time support to concurrency mechanisms, the next step is to formalize and validate the accuracy of the aforementioned functions. At a higher abstraction level, the final step would be to instantiate (evaluate, configure, optimize) the paradigms formalized within the context of structured parallel programming on the basis of $T_{send}$ and $T_{calc}$.
\end{enumerate}
%In general, we advocate that experimentation and extensions to the cost model should proceed in parallel, by always taking into account the \textit{complexity} 
